-
Notifications
You must be signed in to change notification settings - Fork 52
/
Nodes without sibling.cpp
98 lines (88 loc) · 3.02 KB
/
Nodes without sibling.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/*
For a given Binary Tree of type integer, print all the nodes without any siblings.
Input Format:
The first and the only line of input will contain the node data, all separated by a single space. Since -1 is used as an indication whether the left or right node data exist for root, it will not be a part of the node data.
Output Format:
The only line of output prints the node data in a top to down fashion with reference to the root.
Node data in the left subtree will be printed first and then the right subtree.
A single space will separate them all.
Constraints:
1 <= N <= 10^5
Where N is the total number of nodes in the binary tree.
Time Limit: 1 second
Sample Input 1:
5 6 10 2 3 -1 -1 -1 -1 -1 9 -1 -1
Sample Output 1:
9
Sample Input 2:
2 4 5 6 -1 -1 7 20 30 80 90 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 2:
6 7
Explanation of Sample Input 2:
The input tree when represented in a two-dimensional plane, it would look like this:
In respect to the root, node data in the left subtree that satisfy the condition of not having a sibling would be 6, taken in a top-down sequence. Similarly, for the right subtree, 7 is the node data without any sibling.
Since we print the siblings in the left-subtree first and then the siblings from the right subtree, taken in a top-down fashion, we print 6 7.
*/
/*
#include <iostream>
#include <queue>
template <typename T>
class BinaryTreeNode {
public:
T data;
BinaryTreeNode<T>* left;
BinaryTreeNode<T>* right;
BinaryTreeNode(T data) {
this->data = data;
left = NULL;
right = NULL;
}
};
using namespace std;
#include "solution.h"
BinaryTreeNode<int>* takeInput() {
int rootData;
cin >> rootData;
if (rootData == -1) {
return NULL;
}
BinaryTreeNode<int>* root = new BinaryTreeNode<int>(rootData);
queue<BinaryTreeNode<int>*> q;
q.push(root);
while (!q.empty()) {
BinaryTreeNode<int>* currentNode = q.front();
q.pop();
int leftChild, rightChild;
cin >> leftChild;
if (leftChild != -1) {
BinaryTreeNode<int>* leftNode = new BinaryTreeNode<int>(leftChild);
currentNode->left = leftNode;
q.push(leftNode);
}
cin >> rightChild;
if (rightChild != -1) {
BinaryTreeNode<int>* rightNode =
new BinaryTreeNode<int>(rightChild);
currentNode->right = rightNode;
q.push(rightNode);
}
}
return root;
}
int main() {
BinaryTreeNode<int>* root = takeInput();
printNodesWithoutSibling(root);
}
*/
void printNodesWithoutSibling(BinaryTreeNode<int> *root)
{
// Write your code here
if (root == NULL)
return;
if (root->left != NULL && root->right == NULL)
cout << root->left->data << " ";
else if (root->left == NULL && root->right != NULL)
cout << root->right->data << " ";
printNodesWithoutSibling(root->left);
printNodesWithoutSibling(root->right);
}